package www.study.com;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

//组合总和 II https://leetcode.cn/problems/combination-sum-ii/   【非最优解：方式二】
public class code40 {
    public static void main(String[] args) {

    }

    class Solution {

        public List<List<Integer>> res = new ArrayList<>();
        //public Set<String> set = new HashSet<>(); //去重

        public List<List<Integer>> combinationSum2(int[] candidates, int target) {
            Arrays.sort(candidates);
            List<Integer> tmp = new ArrayList<>();
            DFS(tmp,0,target,0,candidates);
            // int[] nums = new int[candidates.length]; //记录去重后的数字
            // int[] cnts = new int[candidates.length]; //记录nums[i]个数
            // int len = 0;
            // int le = 0,rg = 0;
            // while(rg < candidates.length){
            //     while(rg < candidates.length && candidates[rg] == candidates[le]) rg++;
            // nums[len] = candidates[le];
            // cnts[len++] = rg - le;
            // le = rg;
            // }
            // dfs(nums,cnts,len,0,0,target,new ArrayList<>());
            return res;
        }
        //方式二
        public void DFS(List<Integer> tmp,int now,int target,int begin,int[] candidates){
            if(now == target){
                res.add(new ArrayList<>(tmp));
                return;
            }
            for(int i = begin ; i < candidates.length ; i++){
                if(now + candidates[i] > target) return;
                if(i != begin && candidates[i] == candidates[i - 1]) continue;
                tmp.add(candidates[i]);
                DFS(tmp,now+candidates[i],target,i+1,candidates);
                tmp.remove(tmp.size() - 1);
            }
        }
        //方式一
        public void dfs(int[] nums,int[] cnts,int len,int i,int now,int target,List<Integer> list){
            if(i == len || now >= target){
                if(now == target){
                    res.add(new ArrayList(list));
                }
                return;
            }
            int k = 1;
            for( ; (k <= cnts[i]) && (nums[i] * k + now <= target) ; k++){
                list.add(nums[i]);
                dfs(nums,cnts,len,i+1,now+nums[i]*k,target,list);
            }
            k--;
            list.subList(list.size()-k,list.size()).clear();
            dfs(nums,cnts,len,i+1,now,target,list);
        }
    }
}
